package class5;

import common.TreeNode;
import common.TreeNodeUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/description/
 * 二叉树的锯齿形层序遍历
 * 解题思路：
 * 1.利用队列对二叉树进行层遍历
 * 2.每次遍历前，对要判断该层处于 “正向” 或 “逆向” 遍历，重点判断 i 和 j的初始值
 * 3.进入队列保持原样
 */
public class Code20_zigzagLevelOrder {
    public static void main(String[] args) {
        TreeNode cbt = TreeNodeUtils.getCBT();
        List<List<Integer>> lists = zigzagLevelOrder(cbt);
        System.out.println("lists = " + lists);
    }

    static TreeNode[] queue = new TreeNode[2001];
    static int l, r;

    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root != null) {
            l = r = 0;
            queue[r++] = root;

            // false : 从左往右
            // true : 从右往左
            boolean reverse = false;
            while (l < r) {
                int size = r - l;
                List<Integer> list = new ArrayList<>();
                // reverse = false ,左 -> 右
                // reverse = true , 右 -> 左
                // i为起始左边，j为左移右移
                // 控制当前数组是正向遍历还是反向遍历
                for (int i = reverse ? r - 1 : l, j = reverse ? -1 : 1, k = 0; k < size; i += j, k++) {
                    list.add(queue[i].val);
                }
                //
                for (int i = 0; i < size; i++) {
                    TreeNode cur = queue[l++];
                    if (cur.left != null) {
                        queue[r++] = cur.left;
                    }
                    if (cur.right != null) {
                        queue[r++] = cur.right;
                    }
                }
                ans.add(list);
                reverse = !reverse;
            }
        }
        return ans;

    }
}
